package ch01;
//加权quick-union算法
public class WeightQuickUnionFind {
    //触点
    private int[] id;
    //根节点连通分量大小
    private int[] sz;
    //连通分量的数量
    private int count;
    public WeightQuickUnionFind(int n){
        count = n;
        id = new int[n];
        sz = new int[n];

        for (int i = 0; i < n; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }
    //找到触点的根节点
    public int find(int p){
        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }

    //判断p,q是否在同一连通分量内
    public boolean connected(int p, int q) {
        return id[p] == id[q];
    }
    //将p,q相连
    public void union(int p,int q){

        int rootp = find(p);
        int rootq = find(q);
        if (rootp == rootq) {
            return;
        }
        if(sz[rootp]<sz[rootq]){
            id[rootp] = id[rootq];
            sz[rootq] += sz[rootp];
        }else{
            id[rootq] = id[rootp];
            sz[rootp] += sz[rootq];
        }
        count--;


    }

    public int count(){
        return count;
    }

    public static void main(String[] args) {
        WeightQuickUnionFind uf = new WeightQuickUnionFind(10);
        //样例来自《算法第四版》p146
        /*
        p q
        4 3
        3 8
        6 5
        9 4
        2 1
        8 9
        5 0
        7 2
        6 1
        1 0
        6 7
        */


        uf.union(4,3);
        uf.union(3,8);
        uf.union(6,5);
        uf.union(9,4);
        uf.union(2,1);
        uf.union(8,9);
        uf.union(5,0);
        uf.union(7,2);
        uf.union(6,1);
        uf.union(1,0);
        uf.union(6,7);
        System.out.println("count:" + uf.count());
        System.out.println("root0:"+uf.find(0));
        System.out.println("root1:"+uf.find(1));
        System.out.println("root2:"+uf.find(2));
        System.out.println("root3:"+uf.find(3));
        System.out.println("root4:"+uf.find(4));
        System.out.println("root5:"+uf.find(5));
        System.out.println("root6:"+uf.find(6));
        System.out.println("root7:"+uf.find(7));
        System.out.println("root8:"+uf.find(8));
        System.out.println("root9:"+uf.find(9));
       /* 结果
        count:2
        root0:6
        root1:6
        root2:6
        root3:4
        root4:4
        root5:6
        root6:6
        root7:6
        root8:4
        root9:4*/


    }

}
